package com.hspedu.newData.dmsxl.树.二叉树的遍历.层序遍历迭代法.队列;

import com.hspedu.newData.dmsxl.ds.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-04-23 
 * @Version: 1.0
 */

public class LC222完全二叉树的节点个数 {


    // 普通二叉树结点个数，递归法
    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

    // 普通二叉树结点个数，迭代法
    public int countNodes1(TreeNode root){
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        int count = 0;
        while(!queue.isEmpty()){
            int len = queue.size();

            while(len > 0){
                TreeNode node = queue.poll();
                count++;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                len --;
            }
        }
        return count;
    }


    // 满二叉树结点个数，有技巧可以使用
    // 解法，当从某个结点开始，如果是满二叉树，那么按照直接计算的逻辑，不需要全部遍历，如果是非满二叉树就按照普通的方式计算
    public int countNodes2(TreeNode root){
        if (root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;

        int leftDepth = 0;
        while(left!=null){
            left = left.left;
            leftDepth ++;
        }
        int rightDepth = 0;
        while(right != null){
            right = right.right;
            rightDepth ++;
        }

        if (rightDepth == leftDepth){
            return (2<<leftDepth) - 1;
        }
        return countNodes2(root.left) + countNodes2(root.right) + 1;
    }


}
